from DataStructure.Tree import *

""" 自己写的树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

def merge(a: TreeNode,b: TreeNode):
    if a is None:
        return b
    elif b is None:
        return a
    else:
        c = TreeNode(max(a.val, b.val))
        c.left = merge(a.left, b.left)
        c.right = merge(a.right, b.right)
        return c

if __name__ == '__main__':
    al = [3,4,7,1,None,5,8]
    bl = [4,1,6,8,9]
    a = bfs_load(al) # 从堆数列转换成树
    b = bfs_load(bl)
    c = merge(a, b)
    print(c.bfs_show()) # 广度优先打印


class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        
        def in_area(x, y, xs, ys):
            return xs<=x<=xs+2 and ys<=y<=ys+2
        
        def is_valid(x, y, xs, ys, th):
            for xi,yi in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
                if in_area(xi, yi, xs, ys):
                    if abs(image[x][y] - image[xi][yi]) <= th:
                        continue
                    else:
                        return False
            return True
                
            
        m = len(image)
        n = len(image[0])
        res = [[[] for j in range(n)] for i in range(m)]
        for i in range(m-2):
            for j in range(n-2):
                if is_valid(i+1,j,i,j,threshold) and is_valid(i,j+1,i,j,threshold) and is_valid(i+2,j+1,i,j,threshold) and is_valid(i+1,j+2,i,j,threshold):
                    locations = list(zip(range(i, i+3),range(j, j+3)))
                    avg = sum([image[x][y] for x,y in locations]) / 9
                    for x,y in locations:
                        (res[x][y]).append(avg)
        
        for i in range(m):
            for j in range(n):
                res[i][j] = sum(res[i][j])/len(res[i][j]) if res[i][j] else image[i][j]
                